package 零钱兑换;
//给定不同面额的硬币 coins 和一个总金额 amount。
// 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
//

public class Solution
{
    public int coinChange(int[] coins, int amount)
    {
        /*动态规划4步解题法
        1.确定状态
            研究最优策略的最后一步
            转化为子问题
        2.转移方程
            根据子问题的定义直接得到
        3.初始条件和边界情况
            细心，考虑周全
        4.计算顺序
            利用之前的计算结果
        看最后一步，假设最后一枚硬币的面值是k，那么前面的硬币加起来一定是amount-k，转化为求amount-k的最少硬币数
        硬币的币值数是确定的，假设有1,5
        那么f(amount)=f(amount-1)+1和f(amount-5)+1的最小值，核心方程，找到这个方程，就解出了一半
        初始条件，如f(0)=0，边界条件，面值要>0
         */

        //维护一个数组
        int[] arr=new int[amount+1];
        arr[0]=0;
        for (int i = 1; i < amount + 1; i++)
        {
            arr[i]=Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++)
            {
                if (i-coins[j]>=0)
                    arr[i]=Math.min(arr[i],arr[i-coins[j]]+1);
            }
        }
        if (arr[amount]<0||arr[amount]==Integer.MAX_VALUE)
            return -1;
        else
            return arr[amount];
    }
}
